题目分析

设计题，难度一般都不是很大，主要考验我们的思维能力和对数据结构的掌握程度。一般都是栈、队列、堆、哈希表这四个的组合用法。

栈+哈希表

我们想一下数据范围，是1e4，因此单次操作，不能使用O(n)的算法。

因为我们删除元素都是删除最高频率的，而且每次都删除一个元素，因此不会出现频率断档的问题。比如最高频率的元素出现了k次，那么删除元素一定是删除k次的元素，而且删除后，频率最高的一定是k或k - 1次，如果k次的元素只有一个，那么就是k - 1次，如果不止一个，那仍然是k次。

有的小伙伴会提出异议，如果x出现k次，后面又出现了一次x，那么就变成k + 1次，那么k次不就断档了吗？

这种想法是对的，这个也是本题的一个关键点和难点，因为增加元素导致频率上升(从k变成k + 1)，因为有k + 1的存在，不需要考虑原来的频率k。如果动态维护，在删除时还需要从k + 1变成k。而且最关键的是，频率k的元素可能有多个，如果动态维护，还需要查找元素的位置再删除和添加，会打乱原来的顺序，而且时间复杂度是O(n)。因此不能动态维护频率与元素的对应关系。

上面说的比较枯燥，举个例子，1，2，3，4，2这五个元素，当第四个元素遍历结束后。频率1对应的栈是[1, 2, 3, 4]，表示频率1有四个元素。当再次遍历到2时，如果此时修改哈希表为1对应[1, 3, 4]， 2对应[2]，那么需要从1, 2, 3, 4中找到2，这个时间复杂度是O(n)的，因此不能更新，就是1对应[1, 2, 3, 4]，2对应[2]即可。因为1对应的2(第一个)在2对应的2(第二个)删除之前也不会被访问到，所以保留即可。

如果从频率为1开始统计，并用哈希表记录，那么哈希表的长度就是最高的频率。因为不会断档，所以1，2，3… k都会出现，那么弹出元素仅仅需要弹出哈希表长度对应的栈的栈顶即可。仅需要考虑当弹出时，如果栈空则需要删除对应的键即可，如果不删除，下次弹出哈希表的长度对应的栈就会是空。

下面考虑添加元素，添加元素为了第一时间找到添加在哪一个频率上，所以需要维护一个数字与频率的对应关系，可以通过要添加的元素，得到当前该元素的频率k，然后对k + 1频率对应的栈添加元素。

下面的算法中，频率对应的栈用freq2Val表示，含义是频率对应的元素，而元素对应的频率次数用val2Freq表示。

算法的时间复杂度为O(n)，空间复杂度为O(n)。

class FreqStack {
    HashMap<Integer, LinkedList<Integer>> freq2Val = new HashMap<>();

    HashMap<Integer, Integer> val2Freq = new HashMap<>();

    public FreqStack() {

    }

    public void push(int val) {
        val2Freq.put(val, val2Freq.getOrDefault(val, 0) + 1);
        LinkedList<Integer> stack = freq2Val.putIfAbsent(val2Freq.get(val), new LinkedList<>());
        freq2Val.get(val2Freq.get(val)).addLast(val);
    }

    public int pop() {
        int res = freq2Val.get(freq2Val.size()).removeLast();
        val2Freq.put(res, val2Freq.getOrDefault(res, 1) - 1);
        if (freq2Val.get(freq2Val.size()).isEmpty()) {
            freq2Val.remove(freq2Val.size());
        }
        return res;
    }
}

刷题总结

设计题出现的频率不高，但是对数据结构的理解是非常有帮助的，希望小伙伴们不要跳过这些题目。